package com.lry.thompson;

import java.util.*;


/**
 * 给你一个字符串s和一个字符规律p，请你来实现一个支持 '.'和'*'的正则表达式匹配。
 *
 *     '.' 匹配任意单个字符
 *     '*' 匹配零个或多个前面的那一个元素
 *
 * 所谓匹配，是要涵盖整个字符串s的，而不是部分字符串。
 *
 *
 * 示例 1：
 *
 * 输入：s = "aa", p = "a"
 * 输出：false
 * 解释："a" 无法匹配 "aa" 整个字符串。
 *
 * 示例 2:
 *
 * 输入：s = "aa", p = "a*"
 * 输出：true
 * 解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
 *
 * 示例3：
 *
 * 输入：s = "ab", p = ".*"
 * 输出：true
 * 解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/regular-expression-matching
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class RegularMatch {

    Lexer lexer;
    public static void main(String[] args) {
        RegularMatch regularMatch = new RegularMatch();
        System.out.println(regularMatch.isMatch("bbba", ".*b"));
    }

    static class NfaInterpreter {

        private String input;
        private Nfa startNfa;

        public NfaInterpreter(String input,Nfa startNfa) {
            this.input = input;
            this.startNfa = startNfa;
        }


        /**
         * 例如下nfa图：该图只能识别a|b
         *
         *   ↑----ε---> 节点1 ---a---> 节点2 ---ε---↓
         *节点5                                   节点6
         *   ↓_____ε___>节点3 ---b---> 节点4----ε--↑
         *
         *   假设用户输入为a的情况下，解释过程如下：
         *   计算头节点5的ε闭包，close(5) = {1,3,5}
         *   move({1,3,5},'a') = {2}
         *   计算节点2的ε闭包，close(2) = {2，6}
         *   到达终止状态6，算法结束，状态机可以识别a
         *
         *   如果用户输入的是aa呢？
         *   继续上述过程如下：
         *   move({2,6},'a') = {} 发现当输入为a时，节点2，6接受不了，识别失败
         */
        public boolean interpreter(){
            boolean lastAccepted = false;
            Set<Nfa> nfaSet = startNfaClosure();

            for(char c:input.toCharArray()){
                Set<Nfa> move = move(nfaSet, c);

                if(move.isEmpty()){
                    lastAccepted = false;
                    break;
                }

                nfaSet = εClosure(move);
                if(containsEndNfa(nfaSet)){
                    lastAccepted = true;
                }else{
                    lastAccepted = false;
                }
            }

            return lastAccepted;
        }

        /**
         * 判断集合中是否有终态节点
         * @param nfaSet
         * @return
         */
        private boolean containsEndNfa(Set<Nfa> nfaSet){
            if(null==nfaSet || nfaSet.isEmpty()){
                return false;
            }
            for(Nfa nfa:nfaSet){
                if(nfa.isEndNfa()){
                    return true;
                }
            }
            return false;
        }

        private Set<Nfa> startNfaClosure(){
            Set<Nfa> nfaSet = new HashSet<>();
            nfaSet.add(startNfa);
            return εClosure(nfaSet);
        }

        /**
         * 计算ε闭包
         * @param nfaSet
         * @return
         */
        public Set<Nfa> εClosure(Set<Nfa> nfaSet){
            if(null==nfaSet || nfaSet.isEmpty()){
                return Collections.emptySet();
            }

            Stack<Nfa> stack = new Stack<>();
            for (Nfa nfa : nfaSet) {
                stack.push(nfa);
            }

            while(!stack.isEmpty()){
                Nfa nfa = stack.pop();
                if(nfa.edge== 'ε' && nfa.next!=null){
                    if(!nfaSet.contains(nfa.next)){
                        stack.push(nfa.next);
                        nfaSet.add(nfa.next);
                    }
                }
                if(nfa.edge== 'ε' && nfa.next2!=null){
                    if(!nfaSet.contains(nfa.next2)){
                        stack.push(nfa.next2);
                        nfaSet.add(nfa.next2);
                    }
                }
            }
            return nfaSet;
        }

        /**
         * move
         * @param nfaSet
         * @return
         */
        public Set<Nfa> move(Set<Nfa> nfaSet, char c){
            if(null==nfaSet || nfaSet.isEmpty()){
                return Collections.emptySet();
            }
            Set<Nfa> move = new HashSet<>();

            for (Nfa nfa : nfaSet) {
                if(null==nfa.next){
                    continue;
                }
                if(nfa.edge ==c || (nfa.edge== '.' && c>='a' && c<='z')){
                    move.add(nfa.next);
                }
            }

            return move;
        }

    }

    /**
     *
     * @param input a-z
     * @param pattern a-z,.,*
     * @return
     */
    public boolean isMatch(String input, String pattern) {
        lexer = new Lexer(pattern);
        while(lexer.matchToken(Lexer.Token.EOS)){
            lexer.advance();
        }
        NfaPair nfaPair = new NfaPair();
        expr(nfaPair);
        NfaInterpreter nfaInterpreter = new NfaInterpreter(input,nfaPair.start);
        return nfaInterpreter.interpreter();
    }

    public void expr(NfaPair pair){
        cat_expr(pair);
    }

    /**
     * cat_expr -> factor factor...
     *
     * @param pair
     */
    public void cat_expr(NfaPair pair){
        if(!lexer.matchToken(Lexer.Token.EOS)){
            factor(pair);
        }

        /**
         * 连接运算
         * 节点1--a->节点2 连接 节点3--b->节点4
         * 节点1--a->节点2--ε-->节点3--b->节点4
         *  ε表示空
         */
        while(!lexer.matchToken(Lexer.Token.EOS)){
            NfaPair curPair = new NfaPair();
            factor(curPair);

            //使用连接算法将pair和curPair连接起来
            pair.end.next = curPair.start;
            pair.end = curPair.end;
        }
    }


    /**
     * factor -> term | term* | term+ | term?
     *
     * @param pair
     */
    private void factor(NfaPair pair) {
        term(pair);
        //克林闭包* ，>=0个
        if(lexer.matchToken(Lexer.Token.CLOSURE)){
            starClosure(pair);
        }
    }

    /**
     * term -> 单字符 | expr | .通配符 | 字符集如a-z
     * @param pair
     */
    private void term(NfaPair pair)   {
        if(lexer.matchToken(Lexer.Token.L)){
            forSingleCharacter(pair);
        }else if(lexer.matchToken(Lexer.Token.ANY)){
            forDot(pair);
        }
    }

    private void forSingleCharacter(NfaPair pair) {
        pair.start.edge = lexer.getLexeme();
        lexer.advance();
    }

    private void forDot(NfaPair pair) {
        pair.start.edge = '.';
        lexer.advance();
    }


    /**
     * 克林闭包 *
     * 节点1--a-->节点2
     * a*该如何表示？ ε,a,aa,aaa...
     *
     *               -------ε------
     *               ↓            ↑
     * 节点3--ε--->节点1 --a--> 节点2 ---ε-->节点4
     *  |_________________ε__________________↑
     *
     * @param pair
     */
    private void starClosure(NfaPair pair) {
        lexer.advance();

        NfaPair curPair = new NfaPair();
        curPair.start.next = pair.start;
        curPair.start.next2 = curPair.end;

        pair.end.next = pair.start;
        pair.end.next2 = curPair.end;

        pair.start = curPair.start;
        pair.end = curPair.end;
    }

    static class Nfa{
        public char edge = 'ε';//默认节点转换为空
        public Nfa next;
        public Nfa next2;//只有当前nfa节点含有两条EPSILON边 next2才有效

        public boolean isEndNfa(){
            return null==next && null==next2;
        }

    }

    static class NfaPair {
        public Nfa start = new Nfa();
        public Nfa end = new Nfa();

        public NfaPair(){
            start.next = end;
        }
    }

    static class Lexer {

        public enum Token {
            EOS, //正则表达式末尾
            ANY,     // . 通配符
            CLOSURE,      //*
            L        //字符常量
        };

        private Map<Character,Token> tokenMap = new HashMap();

        private Token currentToken = Token.EOS;

        private String pattern;

        private int charIndex = 0;

        private char lexeme;


        public Lexer(String pattern) {
            this.pattern = pattern;
            initTokenMap();
        }

        private void initTokenMap() {
            for (char i = 'a'; i <= 'z'; i++) {
                tokenMap.put(i,Token.L);
            }
            tokenMap.put('.',Token.ANY);
            tokenMap.put('*',Token.CLOSURE);
        }

        public boolean matchToken(Token t) {
            return currentToken == t;
        }

        public char getLexeme() {
            return lexeme;
        }


        public Token getCurrentToken() {
            return currentToken;
        }

        public Token advance(){
            if(charIndex==pattern.length()){
                currentToken = Token.EOS;
                return Token.EOS;
            }
            lexeme = pattern.charAt(charIndex++);
            currentToken = tokenMap.get(lexeme);
            return currentToken;
        }

    }

}
